[x]插入排序

上集解答

import java.util.Queue
import java.util.LinkedList

fun main(){
    var a = arrayOf<Int>(415,3,3,34,542,7,2345,4,32,32,765,5,6,9,658)
    for(i in 0..a.size-1){
        for(j in 0..a.size-2-i){
            if(a[j] > a[j+1]){
                var temp = a[j]
                a[j] = a[j+1]
                a[j+1] = temp
            }
        }
    }
    for(i in 0..a.size-1){
        println("${a[i]}")
    }
}

其實只要在內部回去跑到a.size-2-i就夠了，這是因為跑一趟，就會完成右邊的一格，所以右邊的就不需要再去檢查，就可以省下一些時間了。

插入排序

插入排序也是經典排序之一，他的作法也非常的直覺，時間複雜度是O(N²)。

做法是建立另一個陣列B，然後一個個放入B陣列，在放入時找到他適合的位置。

var size = 15
var a = arrayOf<Int>(415,3,3,34,542,7,2345,4,32,32,765,5,6,9,658)
var b = Array<Int>(size){0}
b[0] = a[0]
for(i in 1..size-1){
    var j=i-1
    while ( j>=0 && b[j]>a[i] ){
        b[j+1]=b[j]
        j-=1
    }
    b[j+1]=a[i]
}

那不過細心的觀眾會發現，其實沒有必要多第二個陣列，我們完全可以在原本陣列做一樣的事情喔。

讓我們施一些小魔法～

fun main(){
    var size = 15
    var a = arrayOf<Int>(415,3,3,34,542,7,2345,4,32,32,765,5,6,9,658)
    for(i in 1..size-1){
        var now_number = a[i]
        var j=i-1
        while ( j>=0 && a[j]>now_number ){
            a[j+1]=a[j]
            j--
        }
        a[j+1]=now_number
    }
    for(i in 1..14){
        print("${a[i]} ")
    }
}

我們的插入排序就完成啦。

要注意由於這次會取代掉正要排序的那格的數字，所以我們需要先存起來喔。